// https://leetcode.cn/problems/valid-sudoku/description/

// 算法思路总结：
// 1. 递归遍历检查数独有效性
// 2. 使用三个标记数组分别记录行、列、九宫格的数字使用
// 3. 遇到冲突立即返回false，全部通过返回true
// 4. 递归处理每个格子，跳过空格继续检查
// 5. 时间复杂度：O(1)，空间复杂度：O(1)（固定81层栈帧+270字节数组）

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    bool visRow[9][10];
    bool visCol[9][10];
    bool visGrip[3][3][10];

    bool isValidSudoku(vector<vector<char>>& board) 
    {
        memset(visRow, 0, sizeof(visRow));
        memset(visCol, 0, sizeof(visCol));
        memset(visGrip, 0, sizeof(visGrip));

        return dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>>& board, int row, int col)
    {
        if (row == 9) return true;
        if (col == 9) return dfs(board, row + 1, 0);
        if (board[row][col] == '.') return dfs(board, row, col + 1);

        int digit = board[row][col] - '0';
        if (visRow[row][digit] == true || visCol[col][digit] == true || visGrip[row / 3][col / 3][digit] == true)
            return false;

        visRow[row][digit] = true;
        visCol[col][digit] = true;
        visGrip[row / 3][col / 3][digit] = true;

        return dfs(board, row, col + 1);
    }

    void printBoard(const vector<vector<char>>& board) 
    {
        cout << "数独棋盘:" << endl;
        for (int i = 0; i < 9; i++) 
        {
            if (i % 3 == 0 && i != 0) 
            {
                cout << "------+-------+------" << endl;
            }
            for (int j = 0; j < 9; j++) 
            {
                if (j % 3 == 0 && j != 0) 
                {
                    cout << "| ";
                }
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main()
{
    vector<vector<char>> board1 = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    vector<vector<char>> board2 = {
        {'8','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    Solution sol;

    cout << sol.isValidSudoku(board1) << endl;
    cout << sol.isValidSudoku(board2) << endl;

    return 0;
}